#include <sys/mman.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include "types.h"
#include "defs.h"
#include "parser.h"
#include "runtime.h"
#include "alloc.h"

struct sxbh default_sxbh;
struct varh default_varh;


struct blkmark *
creatblkmark (void * addr, uint sz, uint tag, struct blkmark * next) {
    struct blkmark * bm = (struct blkmark *) malloc (sizeof (struct blkmark));
    if (bm == NULL) return NULL;
    bm->addr = addr;
    bm->sz = sz;
    bm->tag = tag;
    bm->next = next;
    return bm;
}

#define gettag(allocator) (allocator->nxtag++)

int
sxbhinit (struct sxbh * sh ,uint blknm) {
    void * xmem;
    bzero (sh, sizeof (struct sxbh));
    sh->blknm = blknm;
    #define TOTALSZ (MAX_BLKSZ * blknm)
    xmem = mmap (NULL, TOTALSZ, PROT_EXEC|PROT_READ|PROT_WRITE,
                 MAP_PRIVATE|MAP_ANON,-1,0);
    if (xmem == (void*)-1) {
        return ERROR;
    }
    sh->xmem = xmem;
    uint64 offset = 0;
    struct blkmark * prevmark, * currmark;
    uint64 tag;
    prevmark = NULL;
    currmark = NULL;
    for (;offset < TOTALSZ; offset += MAX_BLKSZ) {
        tag = gettag (sh);
        currmark = creatblkmark (xmem+offset, MAX_BLKSZ, tag, prevmark);
        if (currmark == NULL) return ERROR;
        prevmark = currmark;
    }
    sh->free[21].next = prevmark; // 链接在2M链表上 1 << 21 = 2M
    #undef TOTALSZ
    return SUCCESS;
}
#define MIN_SXBHBLKSZ 64

uint
round_up2exp (uint sz) {
    if (sz == 0) return 1; // 分配0B的情况,这种情况一般不会出现,就姑且为它分配1B吧 ^_^
    uint maxdig = 0;
    uint t = sz;
    while (t != 1) {
        t >>= 1;
        maxdig++;
    }
    if ((sz & ~(1<<maxdig)) != 0) // 有多余位
        maxdig++; // 扩展为2的倍数
    return (1<<maxdig);
}

uint
getindex (uint sz) {
    uint idx = 0;
    while (sz != 1) {
        sz >>= 1;
        idx++;
    }
    return idx;
}

int
is_2exp (uint num) {
    while ((num & 1)==0)
        num >>= 1;
    if (num == 1) return TRUE;
    return FALSE;
}

// 成功返回新blkmark,失败返回(void*)-1
struct blkmark *
split (struct blkmark * bm, struct blkmark bmlist[]) {
    if (bm == NULL || bm->sz<2 || !is_2exp(bm->sz))
        goto error;
    struct blkmark  * splt1, * splt2;
    uint idx = getindex (bm->sz);
    // prevbm = &bmlist[idx];
    // while (prevbm->next && prevbm->next != bm)
    //     prevbm = prevbm->next;
    // //printf ("prevbm->next:%p\n",prevbm->next);
    // //fflush (stdout);
    // if (prevbm->next != NULL) { // (如果在表中就将其删除)
    //     prevbm->next = bm->next; // 将bm从表中删除
    // }
    splt1 = (struct blkmark *) malloc (sizeof(struct blkmark));
    splt2 = (struct blkmark *) malloc (sizeof(struct blkmark));
    if (!splt1 || !splt2) { // 内存分配失败
        free (splt1);
        free (splt2);
        goto error; 
    } 
    splt1->addr = bm->addr;
    splt2->addr = bm->addr + (bm->sz>>1);
    splt1->tag = bm->tag;
    splt2->tag = bm->tag;
    splt1->sz = bm->sz>>1;
    splt2->sz = bm->sz>>1;
    free (bm); // 释放bm
    idx = getindex (splt1->sz);
    splt1->next = bmlist[idx].next; // 将splt1插入链表
    splt2->next = NULL;
    bmlist[idx].next = splt1;
    return splt2;
    error:
    return (void*)-1;
}

struct blkmark * // merge成功返回新blkmark,已插入链表返回NULL,错误返回(void*)-1
merge (struct blkmark * bm, struct blkmark bmlist[]) {
    if (bm == NULL || bm->sz<2 || !is_2exp(bm->sz))
        goto error;
    struct blkmark * prevbm, * buddy, *merged;
    merged = (struct blkmark *) malloc (sizeof (struct blkmark));
    if (merged == NULL) goto error;
    uint idx = getindex (bm->sz);
    prevbm = &bmlist[idx];
    while (prevbm->next && prevbm->next->tag != bm->tag)
        prevbm = prevbm->next;
    if (prevbm->next == NULL) {// buddy不在表中
        bm->next = bmlist[idx].next;
        bmlist[idx].next = bm; // 将bm插入表中, 最后一定会插入到[NR_SBHHD-1]处
        free (merged);
        return NULL; 
    } 
    // 已找到buddy
    buddy = prevbm->next;
    prevbm->next = buddy->next; // 将buddy从表中删除
    merged->addr = (bm->addr<buddy->addr?bm->addr:buddy->addr);
    merged->tag = bm->tag;
    merged->sz = bm->sz<<1;
    merged->next = NULL;
    free (bm);
    free (buddy);
    return merged;
    error:
    return (void*)-1;
}

struct blkmark * // 尝试获得sz大小的blkmark,失败返回NULL,成功返回最近的blkmark,顺便从表中摘除
getblkmark (uint sz, struct blkmark bmlist[]) {
    if (!is_2exp (sz))
        return NULL;
    uint idx;
    idx = getindex (sz);
    struct blkmark * head, *bm;
    if (idx >= NR_SBHHD)
        return NULL;
    head = bmlist;
    while (idx < NR_SBHHD && (head+idx)->next==NULL)
        idx++;
    if (idx == NR_SBHHD) // 无空闲内存
        return NULL;
    bm = (head+idx)->next;
    (head+idx)->next = bm->next;
    //printf ("%p\n",bm);
    return bm;
}

struct blkmark * // 把大块调整成小块
adjustblkmark (struct blkmark* bm, uint sz, struct blkmark bmlist[]) {
    struct blkmark * half;
    if (bm == NULL) return NULL;
    while ((bm->sz>>1) >= sz) {
        half = split (bm, bmlist);
        if (half == (void *)-1) return NULL;
        bm = half;
    }
    return bm;
}

int // 把小块合并成大块
returnblkmark (struct blkmark * bm, struct blkmark bmlist[]) {
    struct blkmark * merged;
    for (;;) {
        merged = merge (bm, bmlist);
        //printf ("merge:%p\n", bm->addr);
        if (merged == (void*)-1) return ERROR;
        if (merged == NULL) return SUCCESS; // 最终一定会返回NULL
        bm = merged;
    }
    return ERROR;
}

uint // 折叠法hasher
hasher (void * addr) {
    uint64 key = (uint64) addr;
    uint idx;
    idx = 0;
    idx = ((key&0xFFFF)>>2)+((key&0xFFFF0000)>>16)+((key&0xFFFF00000000)>>32)+
          ((key&0xFFFF000000000000)>>48);
    return idx % NR_HASHHD;
}

static struct blkmark *
hashfind (struct blkmark bmhmap[], void * addr) {
    uint idx;
    idx = hasher (addr);
    struct blkmark * bm;
    bm = (bmhmap+idx)->next;
    while (bm && bm->addr != addr)
        bm = bm->next;
    if (bm == NULL) return NULL;
    return bm;
}

static int
hashinsert (struct blkmark bmhmap[], struct blkmark * bm) {
    uint idx;
    if (bm == NULL)
        return ERROR;
    idx = hasher (bm->addr);
    struct blkmark * head;
    head = (bmhmap+idx);
    bm->next = head->next;
    head->next = bm;
    return SUCCESS;
}

static int
hashremove (struct blkmark bmhmap[], struct blkmark * bm) {
    uint idx;
    if (bm == NULL)
        return ERROR;
    idx = hasher (bm->addr);
    struct blkmark * prevbm;
    prevbm = (bmhmap+idx);
    while (prevbm->next && prevbm->next != bm)
        prevbm = prevbm->next;
    if (prevbm->next == NULL) return ERROR;
    prevbm->next = bm->next;
    return SUCCESS;
}

void *
xalloc (struct sxbh * sh, uint sz) {
    if (sz >= MAX_BLKSZ) return NULL;
    if (sz < MIN_SXBHBLKSZ)
        sz = MIN_SXBHBLKSZ;
    sz = round_up2exp (sz);
    struct blkmark * bm, * near;
    near = getblkmark (sz, sh->free); // 最近的blk
    if (near == NULL) return NULL;
    if (near->sz == sz) {
        bm = near;
    }  else {
        bm = adjustblkmark (near, sz, sh->free);
    }
    hashinsert (sh->alloc, bm);
    // printf ("xalloc:%p, sz:%u\n",bm->addr, bm->sz);
    return bm->addr;
}

void *
xrealloc (struct sxbh* sh, void * src, uint newsz) {
    void * newaddr;
    newaddr = xalloc (sh, newsz);
    if (newaddr == NULL) return NULL;
    memcpy (newaddr, src, newsz);
    xfree (sh, src);
    return newaddr;
}

int
xfree (struct sxbh* sh, void * addr) {
    struct blkmark * bm;
    if (addr == NULL) return 0;
    bm = hashfind (sh->alloc, addr);
    if (bm == NULL) return ERROR;
    hashremove (sh->alloc, bm);
    // bm已找到
    return returnblkmark (bm, sh->free);
}

/* 变量堆分配函数 */

int
varhinit (struct varh * vh, struct dataseg * ds) {
    bzero (vh, sizeof (struct varh));
    uint blknm = ds->sz / MAX_BLKSZ; 
    void * heap = ds->heap;
    vh->blknm = blknm;
    vh->heap = heap;
    #define TOTALSZ (MAX_BLKSZ * blknm)
    uint64 offset = 0;
    struct blkmark * prevmark, * currmark;
    uint64 tag;
    prevmark = NULL;
    currmark = NULL;
    for (;offset < TOTALSZ; offset += MAX_BLKSZ) {
        tag = gettag (vh);
        currmark = creatblkmark (heap + offset, MAX_BLKSZ, tag, prevmark);
        if (currmark == NULL) return ERROR;
        prevmark = currmark;
    }
    vh->free[21].next = prevmark;
    #undef TOTALSZ
    return SUCCESS;
}

#define MIN_VARHBLKSZ 8

void *
varalloc (struct varh * vh, uint sz) {
    if (sz >= MAX_BLKSZ) return NULL;
    if (sz < MIN_VARHBLKSZ)
        sz = MIN_VARHBLKSZ;
    sz = round_up2exp (sz);
    struct blkmark * bm, * near;
    near = getblkmark (sz, vh->free); // 最近的blk
    if (near == NULL) return NULL;
    if (near->sz == sz) {
        bm = near;
    }  else {
        bm = adjustblkmark (near, sz, vh->free);
    }
    hashinsert (vh->alloc, bm);
    return bm->addr;
}

int
varfree (struct varh* vh, void * addr) {
    struct blkmark * bm;
    if (addr == NULL) return 0;
    bm = hashfind (vh->alloc, addr);
    if (bm == NULL) return ERROR;
    hashremove (vh->alloc, bm); // 从分配表中删除bm
    return returnblkmark (bm, vh->free);
}
